package stack_and_queue;
import java.util.*;
public class Solution10 {
    //下一个更大元素 II(单调栈)
    public int[] nextGreaterElements(int[] nums) {
        //维护一个单调递减栈
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);//全部初始化为-1;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n * 2; i++) {//只用循环两次就可以
            int num = nums[i % n];//解决循环问题
            while(!stack.isEmpty() && num > nums[stack.peek()]) {
                ret[stack.pop()] = num;
            }
            stack.add(i % n);
        }
        return ret;
    }
    //路径总和 III(前缀和)
    class Solution {
        private Map<Long, Integer> map = new HashMap<>();//保存前缀和
        private int target;

        public int pathSum(TreeNode root, int targetSum) {
            this.target = targetSum;
            map.put(0L, 1);//必须要有一个前缀和为0的
            return dfs(root, 0);
        }

        private int dfs(TreeNode root, long sum) {
            if (root == null) {
                return 0;
            }
            sum += root.val;
            //拿到需要的前缀和
            int request = map.getOrDefault(sum - target, 0);//需要的前缀和就是当前和减去目标
            //保存当前前缀树的值
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            //递归看左右子树
            int left = dfs(root.left, sum);
            int right = dfs(root.right, sum);
            //恢复状态
            map.put(sum, map.get(sum) - 1);
            return left + right + request;//返回所有满足的
        }
    }
    //剑指 Offer 09. 用两个栈实现队列
    class CQueue {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        public CQueue() {

        }
        public void appendTail(int value) {
            //新增的时候先检查stack2是否位空，不为空就将所有元素放入stack1;
            while(!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
            stack1.push(value);
        }

        public int deleteHead() {
            //删除前先检查stack2中是否有东西，若有，直接从stack2中拿数据;
            if(!stack2.isEmpty()) {
                return stack2.pop();
            }else {
                //把stack1中的所有元素放入stack2中，然后弹出栈顶
                while(!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
                if(!stack2.isEmpty()) {
                    return stack2.pop();
                } else {
                    return -1;
                }
            }
        }
    }
    //剑指 Offer 31. 栈的压入、弹出序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;//popped的下标
        for(int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty() ? true : false;
    }
    //剑指 Offer 30. 包含min函数的栈
    class MinStack {
        Stack<Integer> stack = new Stack<>();//普通栈
        Stack<Integer> minStack = new Stack<>();//最小栈
        public MinStack() {}
        public void push(int x) {
            if(minStack.isEmpty()) {
                minStack.push(x);
            }else if(x <= minStack.peek()){
                minStack.push(x);
            }
            stack.push(x);
        }

        public void pop() {
            int val = stack.pop();
            if(!minStack.isEmpty() && minStack.peek() == val) {
                minStack.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int min() {
            return minStack.peek();
        }
    }
}
